|
In software, find first set (ffs) or find first one is a bit operation that, given an unsigned machine word, identifies the least significant index or position of the bit set to one in the word. A nearly equivalent operation is count trailing zeros (ctz) or number of trailing zeros (ntz), which counts the number of zero bits following the least significant one bit. The complementary operation that finds the index or position of the most significant set bit is ''log base 2'', so called because it computes the binary logarithm .〔Anderson, (Find the log base 2 of an integer with the MSB N set in O(N) operations (the obvious way) )〕 This is closely related to count leading zeros (clz) or number of leading zeros (nlz), which counts the number of zero bits preceding the most significant one bit. These four operations also have negated versions: * find first zero (ffz), which identifies the index of the least significant zero bit; * count trailing ones, which counts the number of one bits following the least significant zero bit. * count leading ones, which counts the number of one bits preceding the most significant zero bit; * The operation that finds the index of the most significant zero bit, which is a rounded version of the binary logarithm. There are two common variants of find first set, the POSIX definition which starts indexing of bits at 1, herein labelled ffs, and the variant which starts indexing of bits at zero, which is equivalent to ctz and so will be called by that name. == Examples == Given the following 32-bit word: :00000000000000001000000000001000 The count trailing zeros operation would return 3, while the count leading zeros operation returns 16. The count leading zeros operation depends on the word size: if this 32-bit word were truncated to a 16-bit word, count leading zeros would return zero. The find first set operation would return 4, indicating the 4th position from the right. The log base 2 is 15. Similarly, given the following 32-bit word, the bitwise negation of the above word: :11111111111111110111111111110111 The count trailing ones operation would return 3, the count leading ones operation would return 16, and the find first zero operation ffz would return 4. If the word is zero (no bits set), count leading zeros and count trailing zeros both return the number of bits in the word, while ffs returns zero. Both log base 2 and zero-based implementations of find first set generally return an undefined result for the zero word. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Find first set」の詳細全文を読む スポンサード リンク
|